package SubjectQueue;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class TopKFrequent {

/**
 * 难度：中等
 * 
 * 347. 前 K 个高频元素
 * 	给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * 
 * 示例 1:
 * 	输入: nums = [1,1,1,2,2,3], k = 2
 * 	输出: [1,2]
 * 
 * 示例 2:
 * 	输入: nums = [1], k = 1
 * 	输出: [1]
 * 
 * 提示：
 * 	你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 	你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * 	题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 * 	你可以按任意顺序返回答案。
 * 
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TopKFrequent tkf = new TopKFrequent();
		int[] is = tkf.topKFrequent2(new int[] {4,1,-1,2,-1,2,3}, 2);
		for(int i:is) {
			System.out.print(i+",");
		}
	}
	//自己写
	public int[] topKFrequent(int[] nums, int k) {
		//TreeMap<>默认按key升序
		Map<Integer,Integer> map = new TreeMap<>();
		int[] res = new int[k];
		for(int i=0;i<nums.length;i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
		}
		//排序按value升序
		List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
		Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>(){
			public int compare(Map.Entry<Integer,Integer> o1,Map.Entry<Integer,Integer> o2) {
				return o2.getValue().compareTo(o1.getValue());
			}
		});
		//取出前K个key值
		int count=0;
		for(Map.Entry<Integer, Integer> entry:list) {
//			System.out.println(entry.getKey()+":"+entry.getValue()); 
			if(count<k) res[count] = entry.getKey();
			else break;
			count++;
		}
		return res;
    }
	//方法一：堆
	public int[] topKFrequent1(int[] nums, int k) {
	    Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
	    for (int num : nums) {
	        occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
	    }
	    // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
	    PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
	        public int compare(int[] m, int[] n) {
	            return m[1] - n[1];
	        }
	    });
	    //每个数放进优先队列不足k个数，直接放数，大于k个数则比较堆顶比堆顶大才放，最后堆中只保留k个数
	    for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
	        int num = entry.getKey(), count = entry.getValue();
	        if (queue.size() == k) {
	            if (queue.peek()[1] < count) {
	                queue.poll();
	                queue.offer(new int[]{num, count});
	            }
	        } else {
	            queue.offer(new int[]{num, count});
	        }
	    }
	    int[] ret = new int[k];
	    for (int i = 0; i < k; ++i) {
	        ret[i] = queue.poll()[0];
	    }
	    return ret;
	}
	//方法二：基于快速排序
	public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        List<int[]> values = new ArrayList<int[]>();
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            values.add(new int[]{num, count});
        }
        int[] ret = new int[k];
        qsort(values, 0, values.size() - 1, ret, 0, k);
        return ret;
    }
    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
    	//（随机数*（7-0+1））+0
        int picked = (int) (Math.random() * (end - start + 1)) + start;
        //交换数组中第0个和第 随机 个的数
        Collections.swap(values, picked, start);
        
        //pivot等于第1个数的总量
        int pivot = values.get(start)[1];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if (values.get(i)[1] >= pivot) {
            	//如果第i个数总量大于第1个数总量，则跟前一个数互换
                Collections.swap(values, index + 1, i);
                index++;
            }
        }
        //开始跟最后一个数互换
        Collections.swap(values, start, index);

        if (k <= index - start) {
        	//迭代
            qsort(values, start, index - 1, ret, retIndex, k);
        } else {
            for (int i = start; i <= index; i++) {
                ret[retIndex++] = values.get(i)[0];
            }
            if (k > index - start + 1) {
                qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
            }
        }
    }
}
